package leetcode_1_200;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeeCode_95_failed {
    public static TreeNode newT = new TreeNode();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        TreeNode node = findNode(root, 3);
//        copyTree(root, newT);
        List<TreeNode> res = generateTrees(3);
    }

    private static List<TreeNode> generateTrees(int n) {
        List<TreeNode> res = new ArrayList<>();
        int[] ns_0 = new int[n];
        for (int i = 0; i < n; i++) {
            ns_0[i] = i + 1;
        }
        for (int i = 0; i < n; i++) {
            TreeNode r = new TreeNode(i + 1);
            int[] ns = Arrays.copyOf(ns_0, n);
            ns[i] = 0;
            helper(res, r, r, ns);
        }
        return res;
    }

    private static void helper(List<TreeNode> res, TreeNode root, TreeNode r, int[] ns) {
        for (int i = 0; i < ns.length; i++) {
            if (ns[i] != 0) {
                if (ns[i] < r.val) {
                    TreeNode newRoot = new TreeNode();
                    copyTree(root, newRoot);
                    int[] ns_new = Arrays.copyOf(ns, ns.length);
                    TreeNode node = findNode(newRoot, r.val);
                    node.left = new TreeNode(ns_new[i]);
                    ns_new[i] = 0;
                    helper(res, newRoot, node.left, ns_new);
                } else {
                    TreeNode newRoot = new TreeNode();
                    copyTree(root, newRoot);
                    int[] ns_new = Arrays.copyOf(ns, ns.length);
                    TreeNode node = findNode(newRoot, r.val);
                    node.right = new TreeNode(ns_new[i]);
                    ns_new[i] = 0;
                    helper(res, newRoot, node.right, ns_new);
                }
            }
            if (i == ns.length - 1 && ns[ns.length - 1] == 0){
                res.add(root);
            }
        }
    }

    private static TreeNode findNode(TreeNode root, int goal){
        if (root == null)
            return null;
        if (root.val == goal){
            return root;
        }else {
            TreeNode resL = findNode(root.left, goal);
            if (resL != null){
                return resL;
            }else {
                return findNode(root.right, goal);
            }
        }
    }

    private static void copyTree(TreeNode root, TreeNode cp) {
        if (root == null) {
            return;
        }
        cp.val = root.val;
        if (root.left != null) {
            cp.left = new TreeNode();
            copyTree(root.left, cp.left);
        }
        if (root.right != null) {
            cp.right = new TreeNode();
            copyTree(root.right, cp.right);
        }
    }


    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
